package OJPractice;

import java.util.ArrayList;
import java.util.Arrays;

/*
* 复习优先级队列:给一个数组，如何创建一个大根堆
* */
public class Heap {
    // 先不看代码是如何调整大根堆或者是小根堆的，如果是手动调整成大根堆首先是从最后一颗子树开始调整
    // 例如创建大根堆：就是左右孩子和根节点进行比较

    public int[] elem;
    public int usedSize;
    public void init(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSize++;
        }
    }
    
    public void createHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize); //  此时这里的第二个参数的含义是调整结束的下标
            // 但是会发现，每个子树调整的结束的位置是不同的，所以就给 usedSize 就是每次调整
            // 都不会超过这个 usedSize 的意思
            // 这里就是向下调整每一颗子树的意思

        }
    }

    /*
    向下调整的最大时间复杂度：树的高度
    建堆的时间复杂度：O（n）错位相减，结合 二叉树公式
    * 向下调正方法需要传入的参数：父亲下标和每棵树的结束的下标
    * 向下调整的过程：先比较左右孩子，然后将左右孩子最大值和父亲节点进行比较，如果
    * 比父亲节点的值大，就交换他俩的位置，交换完还没结束，此时还要让孩子和父亲指针
    * 继续往上走进行向下调整，直到把当前这颗树调整完成*/
    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;

        // 最起码有左孩子才能进行比较
        while (child < len) {
            // 此时如果没有右孩子就不会走 && 后边的条件了
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
                // 此时这个代码会越界， child + 1 没有这个元素，所以还要加一个判断条件
//            if (elem[child] < elem[child + 1]) {
//                child++;
//            }
            if (elem[child] > elem[parent]) {
                // 此时就是 左右孩子的最大值 > 父亲节点的值
                swap(elem[child], elem[parent]);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    // 堆的插入：向上调整（插入到有效元素的最后一个位置，然后和父亲节点比较，如果插的这个元素值比较大，
    // 就交换他俩的位置）
    // 所以说建堆的方式不只是有一种，如果给了一个数组，此时就是向下调整，但是如果一个元素一个元素的给我
    // 此时就是插入的方法是建堆，就是用的向上调整算法

    // 向上调整建堆的时间复杂度：O（N * logN） 也是用错位相减结合二叉树公式来计算的
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child != 0) {
            if (elem[child] > elem[parent]) {
                swap(elem[child], elem[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public void offer(int val) {
        if (isFull()) {
            // 扩容
            Arrays.copyOf(elem, 2 * elem.length);
        }
        // 扩容完成之后要++
        elem[usedSize++] = val;
        // 向上调整
        shiftUp(usedSize - 1);
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    // 堆的删除
    // 删除堆顶元素的过程：将堆顶元素和最后一个元素进行交换，交换之后usedSize--，之后再将0下标位置的元素
    // 进行向下调整，
    public void pop() {
        if (isEmpty()) return;
        // 交换
        swap(elem[0], elem[usedSize - 1]);
        usedSize--;
        shiftDown(0, usedSize);
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    private void swap(int a, int b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
}
